package lcr;

import java.util.*;

public class Test0108 {
    public static void main(String[] args) {
        new Solution108_1().ladderLength("hit","cog",new ArrayList<>(Arrays.asList("hot","dot","dog","lot","log","cog")));
    }
}

class Solution108_1 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int size = wordList.size();

        HashSet<String> set = new HashSet<>(wordList);

        Deque<String> dp = new ArrayDeque<>(size);
        dp.add(beginWord);

        int count=0;
        ArrayList<String> removeList = new ArrayList<>(size);
        while (!dp.isEmpty()){
            count++;
            int length = dp.size();
            for (int i = 0; i < length; i++) {
                String poll = dp.poll();
                if (endWord.equals(poll)) return count;

                for (String string : set){
                    if (isNext(poll,string)){
                        dp.offer(string);
                        removeList.add(string);
                    }
                }

                set.removeAll(removeList);
                removeList.clear();
            }
        }

        return 0;
    }

    public boolean isNext(String a,String b){
        char[] chars = a.toCharArray();
        char[] chars1 = b.toCharArray();

        boolean flag=true;
        for (int i = 0; i < chars1.length; i++) {
            if (chars[i]!=chars1[i]) {
                if (flag) flag=false;
                else return false;
            }
        }

        return !flag;
    }

}
